package 困难.LRU;

/**
 * 用单链表实现LRU算法（最近最少使用算法）
 * 定义
 * 头结点永远是最久未被访问的元素
 */
public class SingleLinkLRU {

    private ListNode headNode;

    private Integer capacity;

    public SingleLinkLRU(Integer capacity) {
        this.capacity = capacity;
    }

    /**
     * 分类讨论：
     * 1，拜访元素已经存在于链表中
     * 将该元素移至末尾
     * 2，拜访元素未存在链表中
     * a 空间足够-> 直接添加至链表末尾
     * b 空间不足-> 先移除头结点，后添加元素至末尾
     */
    public void visit(int visitValue) {
        if (headNode == null) {
            headNode = new ListNode(visitValue);
            return;
        }
        ListNode tempNode = headNode;  //临时引用，头结点不能丢失
        int count = 0;
        while (tempNode != null) {
            count++;
            if (tempNode.val == visitValue) {
                if (tempNode.next == null) {  //拜访的元素正处于末尾，无需任何操作
                    return;
                }
                tempNode.val = tempNode.next.val;
                tempNode.next = tempNode.next.next;
            }
            if (tempNode.next == null) {  //遍历到末尾
                if (count >= capacity) {  //空间不足
                    headNode = headNode.next;
                }
                tempNode.next = new ListNode(visitValue);
                return;
            }
            tempNode = tempNode.next;
        }
    }

    private boolean isExist(int value) {
        ListNode tempNode = headNode;
        while (tempNode != null) {
            if (tempNode.val == value) {
                return true;
            }
            tempNode = tempNode.next;
        }
        return false;
    }

    public void display() {
        ListNode tempNode = headNode;
        while (tempNode != null) {
            System.out.println(tempNode.val);
            tempNode = tempNode.next;
        }
    }

    public static void main(String[] args) {
        SingleLinkLRU singleLinkLRU = new SingleLinkLRU(4);
        singleLinkLRU.visit(2);
        singleLinkLRU.visit(1);
        singleLinkLRU.visit(3);
        singleLinkLRU.visit(1);
        singleLinkLRU.visit(4);
        singleLinkLRU.display();
    }

}
